803F - Coprime Subsequences - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

long long m=1e9+7;
vector<long long>v(1e5+5),v2(1e5+5);

long long p(long long n){
if(n==1){return 2;}
long long b=p(n/2);
b*=b;b%=m;
if(n%2){b*=2;}
return b%m;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int tst=1;//cin>>tst;
while(tst--){
int a;cin>>a;
while(a--){
    int c;cin>>c;
    for(long long d=1;d*d<=c;d++){
        if(c%d==0){v[d]++;if(d!=c/d){v[c/d]++;}}
    }
}
for(int c=1e5;c>=1;c--){
if(v[c]){v2[c]=(p(v[c])-1);
if(v2[c]<0){v2[c]+=m;}
for(int d=c+c;d<=1e5;d+=c){v2[c]-=v2[d];}
if(v2[c]<0){v2[c]+=m;}
v2[c]%=m;
}
}
if(v2[1]<0){v2[1]+=m;}
cout<<v2[1]%m;
}
return 0;
}